484B - Maximum Value - CodeForces Solution

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <queue>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <cstdio>
#include <stack>
#include <stdlib.h>
#include <fstream>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define all(a) a.begin(), a.end()
#define PI 3.14159265
#define inf 1000000000009
//#define int ll
#define mod 998244353

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
#ifndef ONLINE_JUDGE
	FILE* stream1;	freopen_s(&stream1, "input.txt", "r", stdin);
#endif
	//FILE* stream1;	freopen_s(&stream1, "robots.in", "r", stdin);
	//FILE* stream2;	freopen_s(&stream2, "robots.out", "w", stdout);
	ios::sync_with_stdio(0);cin.tie(0);srand(time(0));
	//**************************************************
	vector<vector<int>> prime(1000001);
	for (int i = 2; i <= 1000000; ++i)
		if (prime[i].size() == 0)
		{
			prime[i].push_back(i);
			for (int j = i * 2; j <= 1000000; j += i)
				prime[j].push_back(i);
		}
	vector<vector<int>> dl(1000001);
	//vector<MC> vecc(1000001);
	vector<int> pr(1000001);
	for (int u = 1;u < dl.size();u++)
	{
		pr[u] = u;
		dl[u].push_back(1);
		for (int i = 0;i < prime[u].size();i++)
		{
			int dll = dl[u].size();
			int now = prime[u][i];
			while (u % now == 0)
			{
				for (int j = 0;j < dll;j++)
					dl[u].push_back(dl[u][j] * now);
				now *= prime[u][i];
			}
		}
	}
	int n;
	cin >> n;
	vector<int> vvu(1000001);
	for (int i = 0;i < n;i++)
	{
		int a;
		//scanf("%d", &a);
		cin >> a;
		vvu[a] = 1;
	}
	//build_tree(vecc);
	for (int u = 1;u <= 1000000;u++)
	{
		int maxpl = -1;
		for (int i = 0;i < dl[u].size();i++)
			if (vvu[dl[u][i]])
				maxpl = max(maxpl, dl[u][i]);
		if (maxpl > -1)
			pr[min(maxpl + u-1,1000000)] = min(pr[min(maxpl + u-1, 1000000)], u);
	}
	vector<int> otvv(1000001);
	otvv[1000000] = pr[1000000];
	for (int i = 999999;i >= 0;i--)
		otvv[i] = min(otvv[i + 1], pr[i]);
	int otv = 0;
	for (int u = 1;u <= 1000000;u++)
		if (vvu[u])
			otv = max(otv, u - otvv[u]);
	cout << otv;
	//*************************************************
	//return 0;
}